package JZ;

import java.util.*;

public class jz38 {
    public static void main(String[] args) {
        String s = "aab";
        Permutation(s);
    }
    static ArrayList<String> ans = new ArrayList<>();
    public static ArrayList<String> Permutation (String str) {
        int[] used = new int[str.length()];
        char[] ch = str.toCharArray();
        Arrays.sort(ch);
        dfs(ch, used);
        System.out.println(ans);
        return ans;
    }
    static List<Character> path = new ArrayList();
    public static void dfs(char[] s, int[] used){
        if(path.size() == s.length){
            String s1 = "";
            for (int i = 0; i < path.size(); i++) {
                s1 += path.get(i);
            }
            ans.add(s1);
            return;
        }
        for (int i = 0; i < s.length; i++) {
            if(used[i] == 1)
                continue;
            if(i != 0 && used[i - 1] == 0 && s[i - 1] == s[i])
                continue;
            used[i] = 1;
            path.add(s[i]);
            dfs(s, used);
            used[i] = 0;
            path.remove(path.size() - 1);
        }
    }
}
